Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Розрахункова робота
з дисципліни “ Комп`ютерна графіка ”
Тема: «Реалізація алгоритму фрактальної кривої»
Теоретичні відомості
Поняття фрактал, фрактальна геометрія і фрактальна графіка, з'явилися в кінці 70-х. Слово фрактал утворено від латинського fractus і в перекладі означає той, що «складається з фрагментів». Воно було запропоноване математиком Бенуа Мандельбротом в 1975 році для позначення нерегулярних, але самоподібних структур. Народження фрактальної геометрії прийнято пов'язувати з виходом в 1977 році книги Мандельброта «The Fractal Geometry of Nature». У його роботах використані наукові результати інших учених, що працювали в 1875 - 1925 роках в тій же області (Пумнкаре, Фату, Жюліа, Кантор, Хаусдорф). Але тільки у наш час вдалося об'єднати їх роботи в єдину систему. Визначення фрактала, дане Мандельбротом: фракталом називається структура, що складається з частин, які в якомусь сенсі подібні до цілого. Самоподібність - одна з основних властивостей фракталів. Об'єкт називають самоподібним, коли збільшені частини об'єкту схожі на сам об'єкт і один на одного.
Розрізняють геометричні і алгебраїчні фрактали. Геометричні фрактали найпоширеніші. У двомірному випадку їх отримують за допомогою деякої ламаної (або поверхні в тривимірному випадку), званої генератором. За один крок алгоритму кожне з відрізків, складових ламаної, замінюється на ламану-генератор, у відповідному масштабі. В результаті багатократного повторення цієї процедури, виходить геометричний фрактал.
Фрактали - об'єкти, що володіють нескінченною складністю, дозволяють розглянути стільки ж своїх деталей поблизу, як і здалеку. Будь-які їх фрагменти, як нескінченно малі, так і нескінченно великі, по будові нічим не відрізняються один від одного. Фрактали можливі не тільки на площині, але і в просторі. Фрактальні структури зустрічаються і в природі. Прикладами фракталів можуть служити крона дерева, прикордонні і берегові лінії, пори в хлібі, дірки в деяких сортах сираі т.д. Поверхня Місяця, виявляється, поблизу виглядає так само, як і здалеку, тільки розміри кратерів інші. Земля - класичний приклад фрактального об'єкту. З космосу вона виглядає як куля. Якщо наближатися до неї, ми виявимо океани, континенти, побережжя і ланцюги гір. Розглядатимемо гори ближче стануть видні ще дрібніші деталі: шматочок землі на поверхні гори в своєму масштабі такий же складний і нерівний, як сама гора. І навіть ще сильніше збільшення покаже крихітні частинки грунту, кожна з яких сама є фрактальним об'єктом. Фрактальну структуру має також Всесвіт.
Для побудови геометричних фрактальних кривих використовуються рекурсивні алгоритми. Рекурсія використовується при вирішенні завдань, які можуть бути розкладені на декілька підзадач. Таким чином, застосування рекурсії доцільне при побудові фрактальних кривих, оскільки вони володіють такою властивістю як самоподібність. Алгоритми побудови фрактальних кривих рекурсивні за своєю природою, і їх набагато простіше вивчати в рекурсивному уявленні.
Алгоритм побудови кривої «Дракона Хартера-Хейтуея»
Для отримання фрактального об'єкту потрібно ввести правила побудови. Хай створюючим елементом будуть два рівні відрізки, сполучених під прямим кутом. У нульовому поколінні замінимо одиничний відрізок на цей створюючий елемент так, щоб кут був зверху. Можна сказати, що при такій заміні відбувається зсув середини ланки. При побудові наступних поколінь виконується правило: найперша зліва ланка замінюється на створюючий елемент так, щоб середина ланки зміщувалася ліворуч від напряму руху, а при заміні наступних ланок напряму зсуву середин відрізань повинні чергуватися. На рис.1 представлено декілька перших поколінь кривої, побудованої за вищеописаним принципом. Гранична фрактальна крива (при n прагнучому до нескінченності) називається дракон...